from typing import List


class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        max = 0
        sum = 0
        for i in gain:
            sum = sum + i
            if sum > max:
                max = sum

        return max


# 方法二
# 以空间换时间  最后再做比较
class Solution2:
    def largestAltitude(self, gain: List[int]) -> int:
        height = [0]
        for g in gain:
            height.append(height[-1]+g)
        return max(height)


if __name__ == '__main__':
    gain = [-5,1,5,0,-7]

    solution = Solution()
    print(solution.largestAltitude(gain))